package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 * https://leetcode.cn/problems/cousins-in-binary-tree/description/
 * ```
 * 993. 二叉树的堂兄弟节点
 * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
 * 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
 * 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
 * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
 *
 *
 * 示例 1：
 * 输入：root = [1,2,3,4], x = 4, y = 3
 * 输出：false
 *
 * 示例 2：
 * 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
 * 输出：true
 * 示例 3：
 * 输入：root = [1,2,3,null,4], x = 2, y = 3
 * 输出：false
 *
 * 提示：
 *
 * 二叉树的节点数介于 2 到 100 之间。
 * 每个节点的值都是唯一的、范围为 1 到 100 的整数。
 *
 * ```
 */
class leetcode_993 {
    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val root = n1
        n1.left = n2
        n1.right = n3

        n2.right = n4
        n3.right = n5

        val actual = isCousins(root, 5, 4)
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    private fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
        /**
        题型：二叉树的层级遍历

        思路：
        若对每一层遍历，若子节点等于X和Y时，记录当前节点作为父节点。若它们的父节点不是同一个，说明是堂兄弟节点。

        空间复杂度：O（N）
        时间复杂度：O（N）
         */

        // 1 确定函数的参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return false
        }
        // 3 确定单层递归的处理逻辑：非递归，层级遍历

        val queue: LinkedList<TreeNode> = LinkedList()
        queue.offer(root)

        while (!queue.isEmpty()) {
            var size: Int = queue.size
            // 记录子节点等于X和Y时的父节点
            var xHeader: TreeNode? = null
            var yHeader: TreeNode? = null

            while (size-- > 0) {
                val node: TreeNode = queue.poll()
                node.left?.let {
                    queue.offer(it)
                    // 若左孩子等于X或Y，那么此节点为父节点
                    if (x == it.`val`) {
                        xHeader = node
                    }
                    if (y == it.`val`) {
                        yHeader = node
                    }
                }
                node.right?.let {
                    queue.offer(it)
                    // 若右孩子等于X或Y，那么此节点为父节点
                    if (x == it.`val`) {
                        xHeader = node
                    }
                    if (y == it.`val`) {
                        yHeader = node
                    }
                }
                // 若X 和 Y 在当前层中找到了，且父节点不同
                if (yHeader != null && xHeader != null && xHeader != yHeader) {
                    return true
                }
            }
        }
        return false
    }
}